P3704 [SDOI2017]数字表格

前置知识：莫比乌斯反演，数论分块

题意

$\prod_{i=1}^n \prod_{j=1}^m f_{ gcd(i,j) }$

其中$f$为斐波拉契数列

Part 1.正常操作

$gcd$可以枚举,令$d=min(n,m)$，上式等价于

$\prod_{k=1}^d\prod_{i=1}^n\prod_{j=1}^mf_k^{[ gcd(i,j)==k ]}$

将重复的$f_k$计算到一起

$\prod_{k=1}^df_k^{\sum_{i=1}^n\sum_{j=1}^m[ gcd(i,j)==k ]}$

$\prod_{k=1}^df_k^{\sum_{i=1}^{ \lfloor n / k \rfloor }\sum_{j=1}^{ \lfloor m / k \rfloor }[ gcd(i,j)==1 ]}$

Part2.毒瘤操作

将指数部分拿出来看：

$\sum_{i=1}^{ \lfloor n / k \rfloor }\sum_{j=1}^{ \lfloor m / k \rfloor }[ gcd(i,j)==1 ]$

有一个结论：

$\sum_{i \mid n}\mu(i)=[n=1]$

证明如下：

1.当$n=1$时显然

2.当$n!=1$时，由唯一分解定理得：$n=p_1^{w_1}p_2^{w_2}...p_k^{w_k}$
由莫比乌斯函数的性质，$\mu(k) \not= 0$当且仅当$k$无平方因子。(由多个质因子相乘)

有$i$个质因子的数有$C_k^i$种取值。

所以只需证

$\sum_{i=0}^k(-1)^iC_k^i=0$

很像二项式定理，将 $x = 1 , y = -1$ 代入即可得证。

代入上式

$\sum_{i=1}^{ \lfloor n / k \rfloor }\sum_{j=1}^{ \lfloor m / k \rfloor }\sum_{s \mid gcd(i,j)}\mu(s)$

改写一下：

$\sum_{i=1}^{ \lfloor n / k \rfloor }\sum_{j=1}^{ \lfloor m / k \rfloor }\sum_{s=1}^{ \lfloor n/k \rfloor }\mu(s)* [s \mid gcd(i,j)]$

将$\mu(s)$向前提：

$\sum_{s=1}^{ \lfloor n/k \rfloor } \mu(s) \sum_{i=1}^{ \lfloor n / k \rfloor }\sum_{j=1}^{ \lfloor m / k \rfloor }[s \mid gcd(i,j)]$

$\sum_{s=1}^{ \lfloor n/k \rfloor } \mu(s)\lfloor \frac{n}{ks} \rfloor \lfloor \frac{m}{ks} \rfloor$

然后，我们得到最终结果为：

$\prod_{k=1}^df_k^{\sum_{s=1}^{ \lfloor n/k \rfloor } \mu(s)\lfloor \frac{n}{ks} \rfloor \lfloor \frac{m}{ks} \rfloor}$

令$T=ks$，则原式等价于：

$\prod_{T=1}^d\prod_{k \mid T }f_k^{\mu(\frac{T}{k})\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor}$

$\lfloor \frac{n}{T} \rfloor , \lfloor \frac{m}{T} \rfloor$与枚举的$k$无关,可以加括号

$\prod_{T=1}^d(\prod_{k \mid T }f_k^{\mu(\frac{T}{k})})^{\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor}$

然后令$F(T)=\prod_{k \mid T }f_k^{\mu(\frac{T}{k})}$,原式化为

$\prod_{T=1}^dF(T)^{\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor}$

似乎就不能化简了

Part3.求解

内部的$F(k)$可以用类似埃筛的思想解决，外部用数论分块，就可以$\Theta(\sqrt{n})$解决了

#include <cstdio>
#include <iostream>
using namespace std;
#define Mod 1000000007

const int MAXN = 1000000;
int k , prime[ MAXN / 10 + 5 ] , mu[ MAXN + 5 ];
bool vis[ MAXN + 5 ];

void sieve( int x ) {
	mu[ 1 ] = 1;
	for( int i = 2 ; i <= x ; i ++ ) {
		if( !vis[ i ] ) {
			prime[ ++ k ] = i;
			mu[ i ] = -1;
		}
		for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= x ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) break;
			mu[ i * prime[ j ] ] = -mu[ i ];
		}
	}
}
int Quick_pow( int x , int po ) {
	int Ans = 1;
	while( po ) {
		if( po % 2 ) 
			Ans = 1ll * Ans * x % Mod;
		x = 1ll * x * x % Mod;
		po /= 2;
	}
	return Ans;
}
int Inv( int x ) {
	return Quick_pow( x , Mod - 2 );
} 

int t , n , m;
int f[ MAXN + 5 ] = { 0 , 1 , 1 } , finv[ MAXN + 5 ] = { 0 , 1 , 1 } , F[ MAXN + 5 ];
void Init( ) {
	sieve( MAXN );
	for( int i = 3 ; i <= MAXN ; i ++ ) {
		f[ i ] = ( f[ i - 1 ] + f[ i - 2 ] ) % Mod;
		finv[ i ] = Inv( f[ i ] ); 
	}
	for( int i = 0 ; i <= MAXN ; i ++ )
		F[ i ] = 1;
	for( int i = 1 ; i <= MAXN ; i ++ ) {
		if( !mu[ i ] ) continue;
		for( int j = i ; j <= MAXN ; j += i )
			F[ j ] = ( 1ll * F[ j ] * ( mu[ i ] == 1 ? f[ j / i ] : finv[ j / i ] ) ) % Mod;
	}
	for( int i = 2 ; i <= MAXN ; i ++ )
		F[ i ] = 1ll * F[ i - 1 ] * F[ i ] % Mod;
}

int solve( int n , int m ) {
	int d = n < m ? n : m , Ans = 1;
	for( int l = 1 , r ; l <= d ; l = r + 1 ) {
		r = min( n / ( n / l ) , m / ( m / l ) );
		Ans = 1ll * Ans * Quick_pow( 1ll * F[ r ] * Inv( F[ l - 1 ] ) % Mod , 1ll * ( n / l ) * ( m / l ) % ( Mod - 1 ) ) % Mod;
	}
	return ( Ans + Mod ) % Mod;
}

int main( ) {
	Init( );	
	scanf("%d",&t);
	while( t -- ) {
		scanf("%d %d",&n,&m);
		printf("%d\n",solve( n , m ));
	}
	return 0;
}